最优比率生成树(0/1 分数规划)
最优比率生成树
0-1 分数规划:
令 a/b 最大 二分枚举最大值 p 则等价为 看是否存在 a/b>p 即 a-pb>0 然后转化为一维问题
求 a-pb 的最大值
a/b>p<=>a-pb>0<=>b/a<p<=>b-pa<0
就是说当 a-pb 的最大值不好求的时候可以转化为求 b-pa 的最小值

const int  maxn =1013;
int n,m,s;
struct node
{
	int x,y,z;
	node(){}
	node(int a,int b,int c){x=a; y=b; z=c;}
}a[maxn];

//cost和dist是两个比率的参数
double cost[maxn][maxn],dist[maxn][maxn],lowcost[maxn];
int pre[maxn],vis[maxn];
double prim(double now)//当前迭代的参数
{
	int i,j,k;
	clr(pre,0);clr(vis,0);
	double mincost,v,allcost=0,alldist=0;
	lowcost[0]=0;
	for(j=1; j<n; j++)
		lowcost[j]=cost[j][0]-now*dist[j][0];
	for(i=1; i<n; i++)
	{
		mincost=INF;
		for(j=1; j<n; j++)
		{
			if(!vis[j] && mincost>lowcost[j])
			{
				mincost=lowcost[j];
				k=j;
			}
		}
		vis[k]=1;
		allcost+=cost[pre[k]][k];
		alldist+=dist[pre[k]][k];
		for(j=0; j<n; j++)
		if(!vis[j])
		{
			if((v=cost[k][j]-now*dist[k][j])<lowcost[j])
			{
				lowcost[j]=v;
				pre[j]=k;
			}
		}
	}
	return allcost/alldist;
}

double get(double a,double b)
{
	return sqrt(a*a+b*b);
}
int main()
{
	//freopen("in","r",stdin);
    int i,j,k,t,cas=0;
	while(scanf("%d",&n),n)
	{
		int x,y,z;
		for(i=0; i<n; i++)	
		{
			scanf("%d%d%d",&x,&y,&z);
			a[i]=node(x,y,z);
		}	
		for(i=0; i<n; i++)
		for(j=i+1; j<n;j++)
		{
			double now=get(0.0+a[i].x-a[j].x,0.0+a[i].y-a[j].y);
			dist[j][i]=dist[i][j]=now;
			cost[j][i]=cost[i][j]=fabs((double)a[i].z-a[j].z);
		}
		double high,low=0;
		while(1)//只用反复迭代下界l，就可以求得结果
		{
			high=prim(low);
			if(fabs(high-low)<0.1)
				break;
			low=high;
		}
		printf("%.3f\n",high);
	}
}
